定义
最多有两棵子树的有序树,称为二叉树。二叉树是一种特殊的树。
性质
这里规定二叉树的根结点的层次为1。
- 性质1:则二叉树的第i 层最多有2i-1个结点(在此二叉树的层次从1开始,i≥1)
- 性质2:深度为k的二叉树最多有2k-1个结点。(k≥1)
- 性质3:对任何一棵二叉树T, 如果其叶结点个数为n0, 度为2的非叶结点个数为n2, 则有
n0 = n2 + 1
- 性质4:具有 n(n>0)个结点的完全二叉树的深度为⎣log2n⎦+1;⎦x⎦表示不超过x的最大整数。
- 性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第⎣l og2n⎦ +1层,每层从左到右),则对任一结点i(1≤i≤n),有:
5.1 (1)如果i=1,则结点i无双亲,是二叉树的根;如果i>1,则其双亲是结点⎣i/2⎦。
5.2 (2) 如果2i<=n, 则结点i的左孩子结点是2i;否则,结点i为叶子结点,无左孩子结点。
5.3 (3)如果2i+1<=n,则结点i的右孩子是结点2i+1; 否则,结点i为叶子结点,无右孩子结点。
完整代码
https://github.com/hisenyuan/btree
二叉链表的实现
1 | package com.hisen.interview.tiger20171110.btree; |
二叉树的各种遍历
1 | package com.hisen.interview.tiger20171110.btree; |